package sort;

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] nums = {9, 8, 10, 6, 5};
        long start = System.currentTimeMillis();
        shellSort(nums);
        long end = System.currentTimeMillis();
        System.out.println(Arrays.toString(nums));
        System.out.println(end - start);
    }

    /**
     * 冒泡排序
     *
     * @param nums
     */
    public static void maopaoSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = nums.length - 1; j >= i; j--) {
                if (nums[j - 1] > nums[j]) {
                    int tem = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = tem;
                }
            }
        }
    }

    /**
     * 选择排序
     * 前 i 个元素已经排序好了
     * 第二个循环遍历找出最小值
     *
     * @param nums
     */
    public static void xuanzeSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            int tem = nums[i];
            nums[i] = nums[min];
            nums[min] = tem;
        }
    }

    /**
     * 插入排序
     * 前 n 个数字排序
     *
     * @param nums
     */
    public static void charuSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) { // 前 i - 1 个元素已经排序好了
            for (int j = i; j >= 1; j--) {
                if (nums[j] >= nums[j - 1]) {
                    break;
                }
                int tem = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tem;
            }
        }
    }

    /**
     * 希尔排序
     *改进的插入排序
     * @param nums
     */
    public static void shellSort(int[] nums) {
        int k = nums.length;
        do {
            k /= 2;
            for (int i = 0; i < nums.length; i++) {
                if (i + k >= nums.length) {
                    break;
                }
                // 这一部分相当于前面的插入排序 , 只是间隔为 k
                for (int j = i + k; j < nums.length; j += k) {
                    for (int l = j; l >= 0; l -= k) {
                        if (l - k < 0 || nums[l] >= nums[l - k]) {
                            break;
                        }
                        int tem = nums[l];
                        nums[l] = nums[l - k];
                        nums[l - k] = tem;
                    }
                }
            }
        } while (k != 1);
    }

    /**
     * 快速排序
     * left 和 right
     * right 开始移动
     * right 移动条件：right 指向的数字要大于开始的数字
     * left 移动条件：left 指向的数字要小于等于开始的数字
     * left 和 right 所指向的数字互换
     *
     * @param nums
     * @param start
     * @param end
     */
    public static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        while (left < right) {
            while (left < right && nums[right] > nums[start]) {
                right--;
            }
            while (left < right && nums[left] <= nums[start]) {
                left++;
            }
            if (left < right) {
                int tem = nums[left];
                nums[left] = nums[right];
                nums[right] = tem;
            }
        }
        int tem = nums[left];
        nums[left] = nums[start];
        nums[start] = tem;
        quickSort(nums, start, left - 1);
        quickSort(nums, left + 1, end);
    }


}
